package sword.chapter1Integer;

/**
 * 只出现一次的数字
 * 两个相同的数异或结果为0
 * 两个不同的数异或结果为1
 * 0异或任何数都等于数字本身
 * a^a^a = 0^a = a
 * a^b^a = b
 *
 * @author K
 * @date 2021-10-12 22:55
 */
public class S4OneNumber {
    public static int singleNumber(int[] nums) {
        // 保存每个位数之和
        int[] bitSums = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                // 一个int有32位，将第i位右移 31-i 等价于将第i位右移到最右边，然后位与1运算，只有1&1=1，否则都是0.多次操作下来就可以计算每位之和
                bitSums[i] += (num >> (31 - i)) & 1;
            }
        }

        int result = 0;
        for (int i = 0; i < 32; i++) {
            // bitSums每位去除掉多余的值，在累加
            // 3，3,3,7
            // 11,11,11，111
            // bitSums结果144  分别对3求余  111即结果7
            result = (result << 1) + bitSums[i] % 3;
        }
        return result;
    }

    public static int singleNumber2(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result ^= nums[i];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3, 3, 3, 2};
        int result = singleNumber(nums);
        System.out.println(result);

//        int[] nums2 = new int[]{3, 3, 2};
//        int result2 = singleNumber2(nums2);
//        System.out.println(result2);
    }
}
